package interview;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description interview
 * @since JDK1.8
 *
 * https://leetcode-cn.com/problems/recursive-mulitply-lcci/
 *
 * 递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。
 * 可以使用加号、减号、位移，但要吝啬一些。
 */
public class RecursionMultiplication {
    public static int multiply(int A, int B) {
        // 这么做的目的是为了减少后续操作
        int a = Math.max(A, B);
        int b = Math.min(A, B);

        // 取出小值最右边的1
        int right = b & (~b + 1);
        // 结果
        int ans = 0;

        while (right != 0) {
            // 算出有多少位
            int bit = 1;
            while ((right >> bit) != 0) {
                bit++;
            }

            // 累加
            ans += (a << (bit - 1));

            // 重新取得最右边的值
            b ^= right;
            right = b & (~b + 1);
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(multiply(30, 4));
    }
}
